public class demo1 {
    class Solution {
        public int rob(int[] nums) {
            int n=nums.length;
            return Math.max((nums[0]+rob1(nums,2,n-2)),(rob1(nums,1,n-1)));
        }
        public int rob1(int[]nums,int left,int right) {
            if(left>right)return 0;
            int n=nums.length;
            int[]f=new int[n];//表示当前位置偷
            int[]g=new int[n];//表示当前位置不偷
            f[left]=nums[left];
            g[left]=0;
            for(int i=left+1;i<=right;i++){
                f[i]=g[i-1]+nums[i];
                g[i]=Math.max(g[i-1],f[i-1]);
            }
            return Math.max(g[right],f[right]);
        }
    }
}
